/**
 * @(#) HeapSort.java Apr 6, 2010 10:07:04 PM
 * Copyright (C) 2009 GeeYee Inc. 60606, Chicago, IL, USA
 * All right reserved
 */
package array;

/**
 * Class <code>HeapSort</code>
 * @author Xiaowen dingxwsimon@gmail.com
 * @since Apr 6, 2010 10:07:04 PM
 *
 */
public class HeapSort
{
	//max heap
	public static void sift(int[] data, int low, int high)  //only sift the data[low] to the right place
	{
		int i, j;
		i = low; //low is the parent
		j = 2*i + 1; // j is the child
		while(j < high)
		{
			if(j+1 < high && data[j] < data[j+1]) j = j+1;//decide left or right child
			
			if(data[i] < data[j]) //if the child if larger than parent, swap
			{
				swap(data, i, j);
				i = j;
				j = 2*i + 1;
			}
			else
				break;
		}
	}
	
	
	public static void heapsort(int[] data)
	{
		int length = data.length;
		for(int i = length/2 - 1; i >= 0; i--)
		{
			sift(data, i, length - 1);
		}
		
		for(int i = length - 1; i >= 1; i--)
		{
			swap(data, 0, i);
			sift(data, 0, i - 1);
		}
	}
	
	public static void swap(int[] data, int i, int j)
	{
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		int[] data =
		{ 2, 13, 1, 12, 11, 7, 9, 10, 20, 6 };
		HeapSort.heapsort(data);
		System.out.println("");

	}

}
